#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int lengthOfLIS(vector<int>& nums) 
{
    //确定dp数组的含义dp[i]:表示以nums[i]结尾的数组的最长递增子序列，注意，一定是nums[i]结尾的数组
    //最后返回dp数组中值最大的即可。
    /*
    index 0 1 2 3 4 5
    nums  1 4 3 4 2 3
    dp    1 2 2 3 2 3
    dp数组的长度和nums的长度一样
    */
    int dp[nums.size()];
    dp[0] = 1;
    for (unsigned int i = 1, len = nums.size(); i < len; i++)
    {
        dp[i] = 1;
        //下面这个for循环主要确定dp[i]的内容
        for(int j = 0; j < i; j++)
        {
            //只比较nums[j] 比 nums[i]小的情况
            if (nums[j] < nums[i])
                dp[i] = dp[j]+1 > dp[i] ? dp[j]+1 : dp[i];
        }
    }
    int max = dp[0];
    for (int i = 0; i < nums.size(); i++)
    {
        cout << "dp[" << i << "] = " << dp[i] << endl;
        if (dp[i] > max) max = dp[i];
    }
    return max;
}
int main()
{
    vector<int> nums;
    nums.push_back(10);
    nums.push_back(9);
    nums.push_back(2);
    nums.push_back(5);
    nums.push_back(3);
    nums.push_back(7);
    nums.push_back(101);
    nums.push_back(18); 
    cout << lengthOfLIS(nums) << endl;
}